package 简单.模拟;

/**
 * 某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）
 * 是一些小写字母的排列。
 * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的
 * 单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/verifying-an-alien-dictionary
 */
public class 验证外星语词典_953 {

    public static void main(String[] args) {

        String[] words = {"ylui", "isxf"};
        System.out.println(isAlienSorted(words, "iophzsywvfktldqbemugarnxjc"));

    }

    /**
     * 用一个数组存储外星字母的权重
     *
     * @param words
     * @param order
     * @return
     */
    public static boolean isAlienSorted(String[] words, String order) {
        int[] weight = new int[26];
        for (int i = 0; i < order.length(); i++) {
            weight[order.charAt(i) - 'a'] = i;
        }
        for (int i = 1; i < words.length; i++) {
            if (!isSort(words[i - 1], words[i], weight)) return false;
        }
        return true;
    }

    public static boolean isSort(String str1, String str2, int[] weight) {
        for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
            if (weight[str2.charAt(i) - 'a'] > weight[str1.charAt(i) - 'a']) {
                return true;
            } else if (weight[str2.charAt(i) - 'a'] < weight[str1.charAt(i) - 'a']) return false;
        }
        // 前缀相等时，str2的长度必须 >= str1的长度，才能符和字典序
        return str2.length() >= str1.length();
    }

}
